class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> memo(128, 0);
        for(auto n : t) memo[n]++;
        int required = t.length();
        int left = 0, right = 0, diff = INT_MAX, head;
        while(right < s.length())
        {
            if(-- memo[s[right]] >= 0) required --;
            right++;
            if(required) continue;
            while(!required)
            {
                if(++memo[s[left]] > 0) required ++;
                left++;
            }
            if(right - left < diff)
            {
                diff = right - left;
                head = left - 1;
            }
        }
        return diff == INT_MAX ? "" : s.substr(head, diff+1);
    }
};
